package com.nowcoder.arithmetic;

/**
 * User: Ruijie Date: 2016/9/2
 */
public class ConstructBinaryTreeFromInorderAndPostorder {
    private static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length!=postorder.length){
            return null;
        }
        if(inorder==null||postorder==null){
            return null;
        }
        return _buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);

    }

    private static TreeNode _buildTree(int[] inorder, int iStart, int iEnd, int[] postorder, int pStart, int pEnd) {
        if(iStart<=iEnd&&pStart<=pEnd){
            int index=getIndex(inorder,postorder[pEnd]);
            TreeNode root=new TreeNode(postorder[pEnd]);
            root.left=_buildTree(inorder,iStart,index-1,postorder,pStart,pEnd-(iEnd-index)-1);
            root.right=_buildTree(inorder,index+1,iEnd,postorder,pEnd-(iEnd-index),pEnd-1);
            return root;
        }
        return null;
    }

    private static int getIndex(int[] inorder, int k) {
        int index=0;
        for(index=0;index<inorder.length;index++){
            if(inorder[index]==k){
                return index;
            }
        }
        return index;
    }

    public static void main(String[] args) {
        int[] inOrder={1,2,3,4,5,6,7};
        int[] posOrder={1,3,2,5,7,6,4};
        TreeNode root=buildTree(inOrder,posOrder);
        InOrderPrintTree(root);
    }

    private static void InOrderPrintTree(TreeNode root) {
        if(root!=null){
            InOrderPrintTree(root.left);
            System.out.print(root.val+"  ");
            InOrderPrintTree(root.right);
        }
    }
}
